Adaptive signal processing is a powerful technique and is often the only technique available when the signals being processed are not deterministic, i.e., not predictable from precise cause and effect. Ohm's Law, for example, is deterministic. Adaptive signals are signals that are alterable or adjustable in accordance with their environment. The automatic gain control (AGC) used in radio and television receivers adjusts sensitivity inversely as the average incoming signal strength. Thus, a wide range of input signal levels is translated into a narrower range of output intensities.
Essential properties of truly adaptive systems are their time-varying, self-adjusting and nonlinear attributes. When the complete range of input conditions for a given system is known, then a design can be fixed and no provision for adaptation is necessary. Examples are low-pass, band-pass and high-pass filters. However, many real-life systems involve parameters whose input conditions vary randomly with time. Examples of closed-loop nonlinear systems that benefit from adaptive adjustment include signal coding, noise reduction, transmission channel equalization, echo or interference cancellation in long transmission channels, speech recognition, image processing and inverse signal modelling.
The manner in which an adaptive filter adjusts itself is described by an adaptive algorithm. An algorithm is a step-by-step procedure for solving a problem (usually mathematical in nature). Many algorithms for performing adaptive filtering exist and each satisfies different performance criteria. Examples are minimization of the total error, i.e., sum squared error, and maximum likelihood optimization. Popular adaptive algorithms are the least mean square (LMS) and the least square (LS) types.
The LMS algorithm is often the algorithm of choice for hardware realization because it solves adaptive filter problems without prior knowledge of higher order statistics of the signal being processed. The LMS algorithm is derived in Chapter 6 of the book entitled "Adaptive Signal Processing", by B. Widrow and S. D. Stearns, Prentice-Hall, Inc., 1985.
There are several known applications of the LMS algorithm in both analog and digital form which use so-called transversal filters. A transversal filter is a time-domain network in which time-spaced samples of a given input signal are plurally weighted and summed to produce as an output signal an idealized replica of the input signal. These applications, however, have invariably used sequential processing or microprocessor control.
FIGS. 1 through 4 illustrate four examples of adaptive filters of the transversal type. In this type of filter the output signal is compared with a desired signal to generate a performance error which is fed back to adjust the characteristics of the filter to achieve more nearly optimal performance. The error symbol at adaptive processor blocks 15 connotes adjustability.
FIG. 1 shows an adaptive filter used as a linear predictor. In this application the adaptive filter 15 is required to predict, on the basis of past sample values of input signal (s) on line 10, a future value of (s). The desired signal in this case is the value of (s) that the filter is trying to predict and the output signal (y) on line 20 is the actual value that the filter obtained through application of the algorithm. An error signal (e) on line 19 is then the prediction error formed in subtracter circuit 12 from the difference between the value (y) in the output of adaptive processor 15 (also appearing on line 20) and input signal (s) provided on line 11. Signal (s) is delayed in delay unit (13) before being applied to processor 15 to allow for processing time. Error signal (e) is a performance indicator which is fed back to processor 15 by way of line 19 to implement the adaptation algorithm. The smaller the value of (e), the better is the prediction performance of the filter. Linear prediction is particularly useful in speech encoding and data compression.
FIG. 2 is configured as a system for system identification. The adaptive filter 15 is here used to identify the impulse response of unknown system 16. Effectively, a finite impulse response (FIR) filter of order M, i.e., having M sampling stages, is used to model the unknown system. The adaptive processor is being adjusted to replicate the impulse response of the unknown system 16. Input signal (s) on line 10 is applied to both unknown system 16 and to adaptive processor 15. The respective outputs (d) and (y) (also appearing on output line 20) of blocks 16 and 15 are combined in subtracter 12 to form error signal (e) on line 19 for control of the processor 15. It is apparent that when error signal (e) becomes zero, the output of unknown system is completely identified. Thus, an echo canceller has been implemented. Input signal (s) can be a speech signal distorted by echoes and error signal (e) can be the desired error-free speech output of the system.
FIG. 3 illustrates the application of the adaptive filter 15 to signal equalization. Input signal (s) on line 10 is assumed to have been altered in traversing a distorting transmission channel (not shown), which also contributes additive noise. In addition to the noise inherent to the unknown system 16, further noise is explicitly introduced on line 23 through combiner 22, which is connected in series between unknown system 16 and adaptive processor 15. The introduced noise is random noise which normally exists when the unknown system communicates with some other system. The added noise helps in masking the inherent noise by correlating with it. The filter needs to find a response that is the inverse of the distortion and noise contributed by the transmission channel. A desired output signal (y) on line 20 is the uncontaminated information signal itself. Input signal (s) is here actually a training signal known to both sides of the transmission channel. Adaptive processor 15 is controlled by error signal (e), which is generated in subtracter 12 and coupled to line 19. Error signal (e) results from taking the difference between input signal (s), after it is delayed in delay unit 13 as signal (d) and a system output signal (y) from processor 15. Adaptive processor 15 adapts during the application of input signal (s), learns the channel characteristics, provides the inverse of the channel distortions, and allows the true information signal to pass through the system to output line 20.
FIG. 4 is an implementation of an adaptive filter to the problem of interference cancellation, such as is present in anti-jamming countermeasures techniques for radar detection systems. A jamming signal (n), friendly or not, is assumed to be overpowering a desired signal (s) on line 10 to such a degree that signal (s) cannot be recognized. The actual signal (s+n) shown on line 10 is a combination of (s) and (n). A second local noise signal (n') is provided as a reference and is assumed to be correlated with the jamming signal (n) to a certain degree. Adaptive processor 15, to which noise (n') is applied by way of line 10, acts to cancel the correlated parts of signals (n) and (n') and replicates as nearly as is feasible signal (s), now assumed to be uncorrelated with either noise signal. The jammed input signal (s+n) has been combined, as shown, in subtracter 12 with an output signal (y) of processor 15 to form error control signal (e) on line 19 for application to processor 15. Signal (y) is then the estimated value of jamming noise signal (n), and error signal (e) is the desired jammed signal (s).
From the foregoing examples, the basic elements of an adaptive system can be recognized:
A signal to be processed;
A desired signal to be emulated; and
An adaptive structure and its implementing algorithm.
FIG. 5 is a block schematic diagram of a known Finite Impulse Response (FIR) digital filter 500 of the sixth order, i.e., capable of providing a total of six samples of an input signal. Five unit delay units 51, each having a unit delay (z.sup.-1), are shown in series with an input signal x(k) on input line 50. Beginning at the input and at each junction or tap between delay units 51 there is connected an adjustable multiplier 52 implementing a weighting factor (w.sub.i) The convoluted sum of the present sample and five delayed input samples taken in a multi-input adder 53 forms the shaped output signal y(k) on output line 55 of the filter. The output signal y(k) is defined as: ##EQU1##
where (m) is the order of the FIR filter and (w.sub.i) are the individual tap or junction weights. The tap weights are either preset according to calculation based on a desired shape or are set according to an LMS algorithm designed to minimize the mean square error adaptively.
FIG. 6 is a block schematic diagram of a known type of digital adaptive filter 600 in third-order form. Adaptive filter 600 has a number of components which are very similar or essentially identical to the filter 500 of FIG. 5 or which have the same reference number with a prime (') added thereafter. Other than the fact that filter 600 is a third-order filter as compared to the filter 500 of FIG. 5, which is a sixth-order filter, the difference between the two is that the gain-control factors of multipliers 52' are automatically set to proper values by the combination of subtracter 67, multipliers 68 and 64 and combiners 63. Each combiner 63 is typically a two-input adder with memory. A feedback path between a first input of each combiner 63 and the output thereof serves to cause combiner 63 to provide at the output thereof a signal which is the sum of the signal applied to the second input and the previous stored signal. Adaptive filter 600 is denoted as such because it generates an error signal e(k) at the output of combiner 67, which effectively and automatically adjusts the gain settings of multipliers 52'.
Line 50' is coupled to the first delay unit 51', to a first input of the first multiplier 52' and to a first input of the first multiplier 64. An output of each of the multipliers 52' is coupled to multi-input adder 53". An output of each of combiners 63 is coupled to a second input of a separate multiplier 52' and to a first input of a separate one of combiners 63. An output of each of multipliers 64 is coupled to a second input of a separate one of combiners 63. A desired signal d(k) is applied to the plus (+) input of combiner 67 and the output signal y(k) of multi-input adder 53' is applied by way of line 55 ' to the minus (-) input of combiner 67. An output of combiner 67 is coupled to second inputs of all of the multipliers 64. Optionally, (as shown by the dashed lines) the error signal e(k) is further adjusted by a gain factor, such as is shown as 2 mu, at combiner 68, whose output is applied to multipliers 64 by way of a dashed line 66.
Adjustable multipliers 52' are controlled by combiners 63 and multipliers 64. Sampled and weighted signals in outputs of multipliers 52' are accumulated in multi-input adder 53", as the corresponding signals at the outputs of multipliers 52 are accumulated in multi-input adder 53 of filter 500 of FIG. 5. An error signal e(k), generated by combiner 67 as the difference between output signal y(k) and desired signal d(k), is then applied to all of multipliers 64. Multipliers 64 act in conjunction with combiners 63 essentially as polarity controls on multipliers 52'. Combiners 63, which each have a feedback connection between an output and the second input thereof, are coupled to an input of multipliers 52' and thus are effectively toggled or ratcheted up and down. The weighting factors in multipliers 52' thus are either incremented positively, decremented negatively, or left unchanged at each clock cycle.
The mean-square error is a quadratic function in terms of the weighting factors (w.sub.i) and can be represented as a parabola or paraboloid, depending on the number of weighting factors involved, so that there is only one global minimum. The goal of the mean-square algorithm is to reach this minimum in some manner. When this minimum is reached, the algorithm is said to have converged. The gradient method is used to find an optimum set of weights or a weight vector. From any beginning weight vector the next weight vector is chosen to be equal to the previous weight vector plus an increment proportional to the negative of the slope of the mean-square error at the previous weight vector. The adaptation equation can be represented as: EQU W.sub.k+1 (i)=W.sub.k (i)+2mu e(k) X.sub.k (k-i), (2)
where
W.sub.k (i)=the previous vector, PA0 W.sub.k+1 (i)=the next vector, PA0 e(k)=the error difference, PA0 X.sub.k (k-i)=the present signal sample at the ith tap, PA0 2mu=the optional gain factor, PA0 k=the time index, and PA0 i=the spatial tap index.
Multi-input adder 53' is generally difficult to implement in silicon because it is complex, typically comprising a plurality of paired adders serially coupled, has a relatively slow response time because of the plurality of serial add operations required in its implementation, and is not easily expandable. Accordingly, the adaptive filter of FIG. 6 suffers from the limitations associated with multi-input adder 53'.
U.S. Pat. No. 3,414,819 (R. W. Lucky), issued Dec. 3, 1968, describes a "Digital Adaptive Equalizer System" which effectively uses a filter having a delay line and a multiple input adder denoted as summer 16. Summer 16 suffers essentially the same limitations as multi-input adder of FIG. 6 herein.
It is desirable to provide an nth-order digital filter and an nth-order adaptive digital filter which can be implemented in silicon, have relatively fast response times and are relatively simple to expand.